1228. Missing Number In Arithmetic Progression
Easy

In some array arr, the values were in arithmetic progression: the values arr[i + 1] - arr[i] are all equal for every 0 <= i < arr.length - 1.

A value from arr was removed that was not the first or last value in the array.

Given arr, return the removed value.

 

Example 1:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

Example 2:

Input: arr = [15,13,12]
Output: 14
Explanation: The previous array was [15,14,13,12].

 

Constraints:

  • 3 <= arr.length <= 1000
  • 0 <= arr[i] <= 105
  • The given array is guaranteed to be a valid array.
Accepted
16.2K
Submissions
31.7K
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Assume the sequence is increasing, what if we find the largest consecutive difference?
Show Hint 2
Is the missing element in the middle of the segment with the largest consecutive difference?
Show Hint 3
For decreasing sequences, just reverse the array and do a similar process.

Average Rating: 4.94 (17 votes)

Premium

Video Solution


 

Solution Article


Intuition

Let's try to find the missing number by linearly scanning the array from start to end. Since we are given that the first and the last numbers cannot be removed, we can use them to get the required difference between each pair of consecutive elements.

difference=last valuefirst valuenumber of values\text{difference} = \dfrac{\text{last value} - \text{first value}}{\text{number of values}}

Once we have the difference we can use it to know what the value at each index is supposed to be. Using the difference as calculated above, and defining initial to be the value at index 0, we have the following:

index 0=initialindex 1=initial+differenceindex 2=initial+2differenceindex 3=initial+3differenceindex n=initial+ndifference \text{index 0} = \text{initial} \\ \text{index 1} = \text{initial} + \text{difference} \\ \text{index 2} = \text{initial} + 2 \cdot \text{difference} \\ \text{index 3} = \text{initial} + 3 \cdot \text{difference} \\ \dots \\ \text{index n} = \text{initial} + \text{n} \cdot \text{difference}

Let's use this to figure out the first missing value in the Arithmetic Progression.

Algorithm

  1. Get the value of difference using first and the last element, difference = last_value - first_value / number_of_values.
  2. Start with the first element as expected value expected = first_element
  3. Run a loop from the first value to the last while checking if the current value is equal to expected. If it is not, then increase expected by difference for the next iteration.
  4. Return the first expected value that doesn't match value in the array`.

Complexity Analysis

  • Time complexity : O(n)O(n) . Where nn is the length of array arr since in the worst case we iterate over the entire array.

  • Space complexity : O(1)O(1). Algorithm requires constant space to execute.



Intuition

In the previous approach we saw that we can get the value required at any index. Let's try to use that property to binary search for the missing value.

We know that there is only one missing number in the given progression. At any index i we can figure out if the value at index i is at the correct position by adding difference times i to the first value in the list, and then comparing it with the value at index i. if they match it means the missing value is in an index on the right of i else it's on the left of i or at i.

This fact can be used to find the index which has the first incorrect number using binary search because if i is the first index with an incorrect number all indices following i would be at incorrect positions (they should be present at 1 position further, since one number is missing) and all numbers before index i will be at correct position. This property is required for binary search to be possible.

Algorithm

  1. Get the value of difference using first and the last element, difference = last_value - first_value / number_of_values.
  2. Start with left index lo = 0 and right index hi = arr.size() - 1.
  3. Pick a mid point index mid = (lo + hi) / 2.
  4. If arr[mid] == first_element + mid * difference. Binary search on the right of mid else binary search on left side of mid including mid itself.
  5. End when there is a single index left as this would be the first index with incorrect value.
  6. Return the value supposed to be at this index which would be first_element + difference * index.

Complexity Analysis

  • Time complexity : O(logn)O(\log n).Where nn is the length of array arr since we cut the search space in half at every iteration.

  • Space complexity : O(1)O(1). Algorithm requires constant space to execute.


Report Article Issue

Comments: 6
TTworld's avatar
Read More

Python one line solution:
Using the sum of the arithmetic progression

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        return int((arr[0] + arr[-1])/2 * (len(arr)+1) - sum(arr))

8
Reply
Share
Report
bals1's avatar
Read More

lol. anything to do with binary search or derivation should medium level problem IMHO.

5
Reply
Share
Report
shogunurus's avatar
Read More

Nice explanation, thanks!

5
Reply
Share
Report
pankajyogi's avatar
Read More

I have not thought about binary search approach. Really an eye-opening solution. So thumb rule is "if array is sorted, then better time complexity is O(log n)"

2
Reply
Share
Report
jca88's avatar
Read More

If think int overflow for binary search (with Java and C++) needs to be addressed when getting the mid. Shouldn't it be lo + (hi - lo)//2? In python, it doesn't matter I think?

0
Reply
Share
Report
sharabiania's avatar
Read More

Easiest solution:

int missingNumber(vector<int>& arr) {
        int k = arr[1] - arr[0];
        int k2 = arr[2] - arr[1];
        
        if(k > 0 && k > k2) swap(k, k2);
        if(k < 0 && k < k2) swap(k, k2);
        for(int i = 0; i + 1 < arr.size(); i++) {
            if(arr[i + 1] - arr[i] != k) return arr[i] + k;
        }
        return arr[0];
    }

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium